#include <iostream>
using namespace std;

template <class K>
struct BSTreeNode{
  typedef BSTreeNode<K> Node;
  Node *_left;
  Node *_right;
  K _key;

  BSTreeNode(const K &key = K())
    :_left(nullptr),
    _right(nullptr),
    _key(key)
  {}
}; 

template <class K>
class BSTree{
  typedef BSTreeNode<K> Node;
  Node *_root = nullptr;
public:
  BSTree(){}

  BSTree(const BSTree<K> &bst){
    _root = _Copy(bst._root);
  }

  BSTree<K>& operator=(BSTree<K> bst){
    swap(bst._root, _root);
    return *this;
  }
  
  ~BSTree(){
    _Destroy(_root);
  }

  void InOrder(){
    _InOrder(_root);  
    cout << endl;
  }
  
  bool Insert(const K &key);
  
  bool rInsert(const K &key){
    return _rInsert(_root, key);
  }
  
  bool Find(const K &key);
  
  bool rFind(const K &key){
    return _rFind(_root, key);
  }

  bool Erase(const K &key);
  
  bool rErase(const K &key){
    return _rErase(_root, key);
  }

private:
  Node* _Copy(Node *root);

  void _Destroy(Node *root);

  void DelNode(Node *parent, Node *cur);

  void _InOrder(Node *root);

  bool _rFind(Node *root, const K &key);

  bool _rInsert(Node* &root, const K &key);

  bool _rErase(Node* &root, const K &key);
};

template <class K>
bool BSTree<K>::Insert(const K &key){
    if(_root == nullptr)
    {
      _root = new Node(key);
      return true;
    }
    Node *cur = _root;
    Node *parent = _root;
    while(cur != nullptr)
    {
      parent = cur;
      if(key > cur->_key)
      {
        cur = cur->_right;
      }
      else if(key < cur->_key)
      {
        cur = cur->_left;
      }
      else{
        return false;
      }
    }
    if(key > parent->_key)
    {
      parent->_right = new Node(key);
    }
    else{
      parent->_left = new Node(key);
    }
    return true;
}
  
template <class K>
    bool BSTree<K>::Find(const K &key){
    if(_root == nullptr) return false;
    Node *cur = _root;
    while(cur != nullptr)
    {
      if(key > cur->_key)
      {
        cur = cur->_right;
      }
      else if(key < cur->_key)
      {
        cur = cur->_left;
      }
      else{
        return true;
      }
    }
    return false;
  }
  
template <class K>
    bool BSTree<K>::Erase(const K &key){
    Node *cur = _root;
    Node *parent = _root; 
    while(cur != nullptr)
    {
      if(key > cur->_key)
      {
        parent = cur; //移动cur之前，记录parent。找到了不移动。
        cur = cur->_right;
      }
      else if(key < cur->_key)
      {
        parent = cur;
        cur = cur->_left;
      }
      else{
        if(cur->_left == nullptr || cur->_right == nullptr)
        {
          DelNode(parent, cur);
        }
        else{
          Node *lmaxp = cur; //如果cur->left就是最大值,lmaxp应该指向cur
          Node *lmax = cur->_left;
          while(lmax->_right != nullptr) 
          {
            lmaxp = lmax;
            lmax = lmax->_right;
          } 
          swap(cur->_key, lmax->_key);
          DelNode(lmaxp, lmax);
        }
        return true; //完成删除马上返回
      }
    }
     return false; 
  }

template <class K>
  BSTreeNode<K>* BSTree<K>::_Copy(Node *root){
    if(root == nullptr) return nullptr;
    Node *copyroot = new Node(root->_key);
    copyroot->_left = _Copy(root->_left);
    copyroot->_right = _Copy(root->_right);
    return copyroot;
  }

template <class K>
  void BSTree<K>::_Destroy(Node *root){
    if(root == nullptr) return;
    _Destroy(root->_left);
    _Destroy(root->_right);
    delete root;
  } 

template <class K>
  void BSTree<K>::DelNode(Node *parent, Node *cur){
    if(cur->_left == nullptr)
    {
      if(cur == _root) //如果要删除的是根节点，需要特殊处理。
      {
        _root = cur->_right;
      }
      else if(parent->_left == cur)
      {
        parent->_left = cur->_right;
      }
      else{
        parent->_right = cur->_right;
      }
    }
    else if(cur->_right == nullptr)
    {
      if(cur == _root)
      {
        _root = cur->_left;
      }
      else if(parent->_left == cur)
      {
        parent->_left = cur->_left;
      }
      else{
        parent->_right = cur->_left;
      }
    }
    delete cur;
  }

template <class K>
  void BSTree<K>::_InOrder(Node *root){
    if(root == nullptr) return;
    _InOrder(root->_left);
    cout << root->_key << " ";
    _InOrder(root->_right);
  }

template <class K>
  bool BSTree<K>::_rFind(Node *root, const K &key){
    if(root == nullptr) return false;
    if(key > root->_key) return _rFind(root->_right, key);
    else if(key < root->_key) return _rFind(root->_left, key);
    else return true;
  }

template <class K>
  bool BSTree<K>::_rInsert(Node* &root, const K &key){
    if(root == nullptr)
    {
      root = new Node(key);
      return true;
    }
    if(key > root->_key) return _rInsert(root->_right, key);
    else if(key < root->_key) return _rInsert(root->_left, key);
    else return false;
  }

template <class K>
  bool BSTree<K>::_rErase(Node* &root, const K &key){
    if(root == nullptr) return false;
    if(key > root->_key) _rErase(root->_right, key);
    else if(key < root->_key) _rErase(root->_left, key);
    else{
      Node *del = root;
      if(root->_left == nullptr)
      {
        root = root->_right;
      }
      else if(root->_right == nullptr)
      {
        root = root->_left; 
      }
      else{
        Node *rmin = root->_right;
        while(rmin->_left!=nullptr)
        {
          rmin = rmin->_left;
        }
        swap(rmin->_key, root->_key);
        return _rErase(root->_right, key);
      }
      delete del;
      return true;
    }
  }
